`
https://leetcode.cn/problems/course-schedule-ii/
`

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
  // 对图进行拓扑排序，排序结果便是课程学习顺序
  // 拓扑排序即是把所有节点“拉平”，且在这个“拉平的”图里面，所有箭头的朝向都是一致的
  // https://labuladong.online/algo/images/topological-sort/top.jpg
  // 如果一个图存在环，那么就无法进行拓扑排序
  // 把图结构后序遍历的结果进行反转，就是拓扑排序的结果

  // 把依赖关系转换为图结构
  const graph = buildGraph(numCourses, prerequisites)

  // 记录在路径上的结点
  const onPath = new Array(numCourses).fill(false)
  // 记录以及访问过的结点
  const visited = new Array(numCourses).fill(false)
  // 记录是否存在环
  let hasCycle = false

  // 记录图后序遍历
  const postorder = []

  const traverse = (cls) => {
    // 如果遇到在以及在路径上的结点，说明有环
    if (onPath[cls]) {
      hasCycle = true
    }
    // 如果有环或者遍历过了，跳过
    if (hasCycle || visited[cls]) {
      return
    }

    // 前序
    visited[cls] = true
    onPath[cls] = true

    // 遍历
    for (const t of graph[cls]) {
      traverse(t)
    }

    // 后序 
    postorder.push(cls)
    onPath[cls] = false
  }

  for (let i = 0; i < numCourses; i++) {
    traverse(i)
  }

  // 如果有环，则不可能完成所有课程
  if (hasCycle) {
    return []
  }

  // 返回后序遍历的翻转结果，即是拓扑排序的结果
  return postorder.reverse()

};

function buildGraph(numCourses, prerequisites) {
  const graph = new Array(numCourses).fill(null).map(() => [])
  for (const edge of prerequisites) {
    const from = edge[1], to = edge[0]
    graph[from].push(to)
  }
  return graph
}